package tinybase.ix;

import java.nio.ByteBuffer;
import java.nio.charset.Charset;
import java.util.Arrays;

import org.junit.Assert;

import tinybase.basic.ByteArrayUtility;
import tinybase.basic.BytePointer;
import tinybase.basic.IntegerWrapper;
import tinybase.basic.RC;
import tinybase.basic.RedBase;
import tinybase.basic.RedBase.AttrType;
import tinybase.pf.PF_FileHandle;
import tinybase.pf.PF_PageHandle;
import tinybase.pf.PageNum;
import tinybase.pf.Pf;
import tinybase.pf.Slot;
import tinybase.rm.RID;
import tinybase.rm.RM_Internal;

public class IndexHandle {

	/*
	 * private attributes
	 */
	private PF_FileHandle pfFileHandle;
	private AttrType attrType;
	private int attrLength;
	private int distinctValsInc;
	private int depthInc;

	/*
	 * public attributes and functions
	 */
	public void setDistinctValsInc(int distinctValsInc) {
		this.distinctValsInc = distinctValsInc;
	}

	public void setDepthInc(int depthInc) {
		this.depthInc = depthInc;
	}

	public void setAttrType(int attrType) {
		this.attrType.setValue(attrType);
	}

	public void setAttrType(AttrType attrType) {
		this.attrType = attrType;
	}

	public AttrType getAttrType() {
		return attrType;
	}

	public PF_FileHandle getPfFileHandle() {
		return pfFileHandle;
	}

	public void setAttrLength(int attrLength) {
		this.attrLength = attrLength;
	}

	public int getAttrLength() {
		return attrLength;
	}

	//
	// IX_IndexHandle
	//
	// Desc: Default constructor
	//
	public IndexHandle() {
		// Initialize member variables
		pfFileHandle = new PF_FileHandle();
		attrType = AttrType.INT;
		attrLength = 0;
		distinctValsInc = 0;
		depthInc = 0;
	}

	//
	// InsertEntry
	//
	// Desc: Insert a new index entry to index.
	// In: pData - key value
	// rid - record identifier
	// Ret: IX_NULLPOINTER, RM_INVIABLERID
	//
	// Insert a new index entry
	public RC insertEntry(Object data, RID rid) {
		RC rc = RC.SUCCESS;
		PageNum pageNum = new PageNum();
		BytePointer tmp = new BytePointer();

		// Sanity Check: pData must not be NULL
		if (data == null)
			// Test: null data
			return RC.IX_NULLPOINTER;

		// Sanity Check: RID must be viable
		if ((rc = rid.getPageNum(pageNum)) != RC.SUCCESS)
			// Test: invalid rid
			return rc;

		// Insert the new entry to the B+ tree
		if ((rc = insertEntryToNode(0, data, rid, tmp, pageNum)) != RC.SUCCESS)
			return rc;

		// Return OK
		return RC.SUCCESS;
	}

	// Delete a new index entry
	public RC deleteEntry(Object data, RID rid) {
		RC rc = RC.SUCCESS;
		PageNum pageNum = new PageNum();
		BytePointer tmp = new BytePointer();

		// Sanity Check: pData must not be NULL
		if (data == null)
			// Test: NULL data
			return RC.IX_NULLPOINTER;

		// Sanity Check: RID must be viable
		if ((rc = rid.getPageNum(pageNum)) != RC.SUCCESS)
			// Test : inviable rid
			return rc;

		// Delete the entry from the B+ tree
		if ((rc = deleteEntryAtNode(0, data, rid, tmp, pageNum)) != RC.SUCCESS)
			// Test: unopened indexHandle
			return rc;

		// if define debug_ix
		Assert.assertTrue(tmp.getArray() == null);
		// end if

		// Return OK
		return RC.SUCCESS;
	}

	// Force index files to disk
	//
	// ForcePages
	//
	// Desc:
	// Ret: PF return code
	//
	public RC forcePages() {
		RC rc = RC.SUCCESS;

		// Call PF_FileHandle::forcePages()
		if ((rc = pfFileHandle.forcePages(RedBase.ALL_PAGES)) != RC.SUCCESS)
			return rc;

		// Return OK
		return RC.SUCCESS;
	}

	//
	// deltaDisinctVals
	//
	// Ret: distinctValsInc
	//
	// Returns distinctValsInc
	public int deltaDistinctVals() {
		return distinctValsInc;
	}

	//
	// deltaDepth
	//
	// Ret: depthInc
	//
	// Returns depthInc
	public int deltaDepth() {
		return depthInc;
	}

	// Get the first 4 bytes of Min|Max key (for statistics)

	//
	// GetMinKey
	//
	public RC getMinKey(IntegerWrapper key, PageNum nodeNum) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer node = new BytePointer();

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum.getPageNum(), pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
			return rc;

		IX_PageHdr ixPageHdr = new IX_PageHdr(node.getArray(),
				PF_PageHandle.DATASTART_OFFSET);

		// Current node is LEAF node
		if ((ixPageHdr.flags & IX_Internal.IX_LEAF_NODE) == 1) {
			// Copy the smallest key
			if (ixPageHdr.numKeys == 0) {
				key.setFromBytes(new byte[4]);
			} else if (attrLength < 4) {
				key.setValue(0);
				key.setFromBytes(Arrays.copyOf(leafKey(node.getArray(), 0),
						attrLength));
			} else {
				key.setFromBytes(Arrays.copyOf(leafKey(node.getArray(), 0), 4));
			}

			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum.getPageNum())) != RC.SUCCESS)
				return rc;
		} else {
			// Current node is INTERNAL node
			// Follow the leftmost pointer
			PageNum childNodeNum = new PageNum();
			childNodeNum.getFromByte(internalPtr(node.getArray(), 0));

			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum.getPageNum())) != RC.SUCCESS)
				return rc;

			// Recursion
			if ((rc = getMinKey(key, childNodeNum)) != RC.SUCCESS)
				return rc;
		}

		// Return OK
		return RC.SUCCESS;
	}

	//
	// GetMaxKey
	//
	public RC getMaxKey(IntegerWrapper key, PageNum nodeNum) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer node = new BytePointer();
		int numKeys = 0;

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum.getPageNum(), pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
			return rc;

		IX_PageHdr ixPageHdr = new IX_PageHdr(node.getArray(),
				PF_PageHandle.DATASTART_OFFSET);

		numKeys = ixPageHdr.numKeys;

		// Current node is LEAF node
		if ((ixPageHdr.flags & IX_Internal.IX_LEAF_NODE) == 1) {
			// Copy the largest key
			if (numKeys == 0) {
				key.setFromBytes(new byte[4]);
			} else if (attrLength < 4) {
				key.setValue(0);
				key.setFromBytes(Arrays.copyOf(
						leafKey(node.getArray(), numKeys - 1), attrLength));
			} else {
				key.setFromBytes(Arrays.copyOf(
						leafKey(node.getArray(), numKeys - 1), 4));
			}

			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum.getPageNum())) != RC.SUCCESS)
				return rc;
		} else {
			// Current node is INTERNAL node
			// Follow the rightmost pointer
			PageNum childNodeNum = new PageNum();
			childNodeNum.getFromByte(internalPtr(node.getArray(), numKeys));

			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum.getPageNum())) != RC.SUCCESS)
				return rc;

			// Recursion
			if ((rc = getMaxKey(key, childNodeNum)) != RC.SUCCESS)
				return rc;
		}

		// Return OK
		return RC.SUCCESS;
	}

	// if define DEBUG_IX
	//
	// PrintNode
	//
	public RC printNode(PageNum pNum) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer node = new BytePointer();
		int j = 0;
		int i = 0;
		float f = 0;
		byte[] s = new byte[RedBase.MAXSTRINGLEN + 1];

		// Pin
		if ((rc = pfFileHandle.getThisPage(pNum.getPageNum(), pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
			return rc;

		IX_PageHdr ixPageHdr = new IX_PageHdr(node.getArray(),
				PF_PageHandle.DATASTART_OFFSET);

		// Current node is LEAF node
		if ((ixPageHdr.flags & IX_Internal.IX_LEAF_NODE) == 1) {
			RID rid = new RID();
			PageNum pn = new PageNum();
			Slot sn = new Slot(0);

			System.out.printf("Leaf (%d) %d (%d): ", ixPageHdr.prevNode,
					pNum.getPageNum(), ixPageHdr.nextNode);

			for (j = 0; j < ixPageHdr.numKeys; j++) {
				ByteBuffer buf = null;
				buf = ByteBuffer.wrap(leafKey(node.getArray(), j), 0, 4);
				switch (attrType) {
				case INT:
					i = buf.getInt();
					System.out.printf("[%d]", i);
					break;
				case FLOAT:
					f = buf.getFloat();
					System.out.printf("[%f]", f);
					break;
				case STRING:
					s = Arrays.copyOf(leafKey(node.getArray(), j), attrLength);
					System.out.printf("[%s]", s);
					break;
				}

				rid.getFromBytes(leafRID(node.getArray(), j));
				rid.getPageNum(pn);
				rid.getSlotNum(sn);
				System.out
						.printf("(%d,%d)", pn.getPageNum(), sn.getSlotValue());
			}
			System.out.println();
		} else {
			// Current node is INTERNAL node
			PageNum pn = new PageNum();

			System.out.printf("Intl (%d) %u (%d): ", ixPageHdr.prevNode,
					pNum.getPageNum(), ixPageHdr.nextNode);

			for (j = 0; j < ixPageHdr.numKeys; j++) {
				pn.getFromByte(internalPtr(node.getArray(), j));
				System.out.printf("%u ", pn.getPageNum());
				ByteBuffer buf = ByteBuffer.wrap(
						internalKey(node.getArray(), j), 0, 4);
				switch (attrType) {
				case INT:
					i = buf.getInt();
					System.out.printf("<%d>", i);
					break;
				case FLOAT:
					f = buf.getFloat();
					System.out.printf("<%f>", f);
					break;
				case STRING:
					s = Arrays.copyOf(internalKey(node.getArray(), j),
							attrLength);
					System.out.printf("<%s>", s);
					break;
				}
			}
			pn.getFromByte(internalPtr(node.getArray(), j));
			System.out.printf("%u\n", pn.getPageNum());
		}

		// Unpin
		if ((rc = pfFileHandle.unpinPage(pNum.getPageNum())) != RC.SUCCESS)
			return rc;

		// Return OK
		return RC.SUCCESS;
	}

	//
	// VerifyOrder
	//
	public RC verifyOrder(int nodeNum) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer node = new BytePointer();
		int j = 0;
		int i = 0;
		int iOld = 0x80000000;
		float f = 0;
		float fOld = Float.MAX_VALUE;
		int nextNode = PageNum.PF_PAGE_UNSET;
		int prevNode = IX_Internal.IX_NO_MORE_NODE;

		// Pin
		// zliu 112 pageNum -> int
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
			return rc;

		IX_PageHdr ixPageHdr = new IX_PageHdr(node.getArray(),
				PF_PageHandle.DATASTART_OFFSET);

		// Current node is LEAF node
		if ((ixPageHdr.flags & IX_Internal.IX_LEAF_NODE) != 0) {
			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
				return rc;

			do {
				// Pin
				if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS)
					return rc;
				if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
					return rc;
				// zliu 113 Should reset IX_PageHdr when newly load data
				ixPageHdr = new IX_PageHdr(node.getArray(),
						PF_PageHandle.DATASTART_OFFSET);
				//
				Assert.assertTrue(nodeNum == 0
						|| ixPageHdr.prevNode == prevNode);

				for (j = 0; j < ixPageHdr.numKeys; j++) {
					ByteBuffer buf = ByteBuffer
							.wrap(leafKey(node.getArray(), j));
					switch (attrType) {
					case INT:
						i = buf.getInt();
						// System.out.println("iOld= " + iOld);
						// System.out.println("i= " + i);
						Assert.assertTrue(iOld <= i);
						iOld = i;
						break;
					case FLOAT:
						f = buf.getFloat();
						// System.out.println("fOld = " + fOld);
						// System.out.println("f = " + f);
						Assert.assertTrue(fOld <= f);
						fOld = f;
						break;
					case STRING:
						String s = new String(leafKey(node.getArray(), j),
								Charset.forName("ASCII"));
						// System.out.println(s);
						break;
					}

					RID rid = new RID();
					PageNum pn = new PageNum();
					Slot sn = new Slot(0);

					rid.getFromBytes(leafRID(node.getArray(), j));
					rid.getPageNum(pn);
					rid.getSlotNum(sn);
				}
				nextNode = ixPageHdr.nextNode;

				// Unpin
				if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
					return rc;

				if (nodeNum == 0)
					break;

				prevNode = nodeNum;
				nodeNum = nextNode;
			} while (nodeNum != IX_Internal.IX_NO_MORE_NODE);
		} else {
			// Current node is INTERNAL node
			int childeNodeNum = ByteBuffer
					.wrap(internalPtr(node.getArray(), 0)).getInt(0);

			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
				return rc;

			// Recursion
			if ((rc = verifyOrder(childeNodeNum)) != RC.SUCCESS)
				return rc;
		}

		// Return OK
		return RC.SUCCESS;
	}

	//
	// VerifyStructure
	//
	public RC verifyStructure(int nodeNum) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer node = new BytePointer();

		// Pin
		// zliu 111
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
			return rc;

		IX_PageHdr ixPageHdr = new IX_PageHdr(node.getArray(),
				PF_PageHandle.DATASTART_OFFSET);

		// Current node is LEAF node
		if ((ixPageHdr.flags & IX_Internal.IX_LEAF_NODE) == 1) {
			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
				return rc;
		} else {
			// Current node is INTERNAL node
			int j = 0;
			for (j = 0; j < ixPageHdr.numKeys; j++) {
				BytePointer key = new BytePointer();

				int childNodeNum = ByteBuffer.wrap(
						(internalPtr(node.getArray(), j + 1))).getInt(0);
				if ((rc = getSmallestKey(childNodeNum, key)) != RC.SUCCESS)
					return rc;
				// whether we need to restraint the length
				// assert(memcmp(key, InternalKey(pNode, j), attrLength) == 0);
				Assert.assertTrue(Arrays.equals(key.getArray(),
						internalKey(node.getArray(), j)));
			}

			for (j = 0; j <= ixPageHdr.numKeys; j++) {
				int childNodeNum = ByteBuffer.wrap(
						(internalPtr(node.getArray(), j))).getInt(0);
				if ((rc = verifyStructure(childNodeNum)) != RC.SUCCESS)
					return rc;
			}

			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
				return rc;
		}

		// Return OK
		return RC.SUCCESS;
	}

	//
	// GetSmallestKey
	//
	public RC getSmallestKey(int nodeNum, BytePointer key) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer node = new BytePointer();

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
			return rc;

		IX_PageHdr ixPageHdr = new IX_PageHdr(node.getArray(),
				PF_PageHandle.DATASTART_OFFSET);

		// Current node is LEAF node
		if ((ixPageHdr.flags & IX_Internal.IX_LEAF_NODE) == 1) {
			// Copy the smallest key
			key.setArray(new byte[this.attrLength]);
			System.arraycopy(leafKey(node.getArray(), 0), 0, key.getArray(), 0,
					attrLength);

			// Unin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
				return rc;
		} else {
			// Current node is INTERNAL node
			// Follow the most left pointer

			int childNodeNum = ByteBuffer.wrap(
					(internalPtr(node.getArray(), 0))).getInt(0);

			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
				return rc;

			// Recursion
			if ((rc = getSmallestKey(childNodeNum, key)) != RC.SUCCESS)
				return rc;
		}

		// Return OK
		return RC.SUCCESS;
	}

	// end if

	/*
	 * private functions
	 */

	// // Copy constructor
	// private IndexHandle(IndexHandle indexHandle) {
	//
	// }

	//
	// InternalEntrySize, InternalKey, InternalPtr
	//
	// Desc: Compute various size/pointer for an internal node
	// In: base - pointer returned by PF_PageHandle.GetData()
	// idx - entry index
	// Ret:
	//

	private final int internalEntrySize() {
		return PageNum.PAGENUM_SIZE + attrLength;
	}

	private final byte[] internalPtr(byte[] base, int idx) {
		byte[] arr = Arrays.copyOfRange(base, getInternalPtrOffset(idx),
				getInternalKeyOffset(idx));
		return arr;
	}

	/**
	 * Copy the value of the key
	 * 
	 * @param base
	 *            , the page data's starting address
	 * @param idx
	 *            , the index of entry
	 * @return a copy of the key
	 */
	private final byte[] internalKey(byte[] base, int idx) {
		byte[] arr = Arrays.copyOfRange(base, getInternalKeyOffset(idx),
				getInternalPtrOffset(idx + 1));
		return arr;
	}

	private final void setInternalPtr(byte[] base, int idx, byte[] arr) {
		if (arr.length != PageNum.PAGENUM_SIZE)
			System.out.println("Array length not equal to EntrySize!");
		else {
			int offset = getInternalPtrOffset(idx);
			for (int i = 0; i < PageNum.PAGENUM_SIZE; i++)
				base[offset + i] = arr[i];
		}
	}

	private final void setInternalKey(byte[] base, int idx, byte[] arr) {
		Assert.assertTrue(arr.length == attrLength);
		System.arraycopy(arr, 0, base, getInternalKeyOffset(idx), attrLength);
	}

	private final void copyInternalKey(byte[] destBase, int destIdx,
			byte[] srcBase, int srcIdx, int length) {
		int destOffset = getInternalKeyOffset(destIdx);
		int srcOffset = getInternalKeyOffset(srcIdx);

		for (int i = 0; i < length; i++)
			destBase[destOffset + i] = srcBase[srcOffset + i];
	}

	private final void copyInternalPtr(byte[] dest, int destIdx, byte[] src,
			int srcIdx, int length) {
		System.arraycopy(src, getInternalPtrOffset(srcIdx), dest,
				getInternalPtrOffset(destIdx), length);
	}

	private final void moveInternalKey(byte[] base, int srcIdx, int destIdx,
			int length) {
		int destOffset = getInternalKeyOffset(destIdx);
		int srcOffset = getInternalKeyOffset(srcIdx);

		if (srcIdx < destIdx) {
			for (int i = length - 1; i >= 0; i--)
				base[destOffset + i] = base[srcOffset + i];

			// for (int i = 0; i < internalEntrySize(); i++)
			// base[srcOffset + i] = (byte) '0';
			Arrays.fill(base, srcOffset, srcOffset + internalEntrySize(),
					(byte) 0);
		} else
			System.out.println("Wrong Index when moving InternalKey!");
	}

	private int getInternalEntrySize() {
		return PageNum.PAGENUM_SIZE + this.attrLength;
	}

	/**
	 * Compute the offset of "idx"th Entry
	 * 
	 * @param idx
	 *            : index of the Entry Objective
	 * @return: index of the starting data in pData
	 */
	private int getInternalPtrOffset(int idx) {
		return PF_PageHandle.DATASTART_OFFSET + IX_Internal.IX_PAGEHDR_SIZE
				+ idx * this.getInternalEntrySize();
	}

	private int getInternalKeyOffset(int idx) {
		return getInternalPtrOffset(idx) + PageNum.PAGENUM_SIZE;
	}

	public RC errReturn(RC rc) {
		Assert.assertTrue(false);
		return rc;
	}

	//
	// LeafEntrySize, LeafKey, LeafRID
	//
	// Desc: Compute various size/pointer for a leaf node
	// In: base - pointer returned by PF_PageHandle.GetData()
	// idx - entry index
	// Ret:
	//

	private final int leafEntrySize() {
		return attrLength + RM_Internal.RM_RID_SIZE;
	}

	public final byte[] leafKey(byte[] base, int idx) {
		byte[] arr = Arrays.copyOfRange(base, getLeafKeyOffset(idx),
				getLeafRIDOffset(idx));
		return arr;
	}

	private final byte[] leafRID(byte[] base, int idx) {
		byte[] arr = Arrays.copyOfRange(base, getLeafRIDOffset(idx),
				getLeafKeyOffset(idx + 1));
		return arr;
	}

	private final void setLeafKey(byte[] base, int idx, Object data, int length) {
		int offset = getLeafKeyOffset(idx);
		// System.out.println("data all :" + data);
		if (data instanceof Integer) {
			ByteBuffer buf = ByteBuffer.wrap(base);
			// System.out.println("data is: " + (Integer)data);
			buf.putInt(offset, (Integer) data);
			int tmp = buf.getInt(offset);
			// System.out.println("Get data: " + tmp);
		} else {
			byte[] tmp = (byte[]) data;
			// System.out.println(tmp);
			for (int i = 0; i < length; i++)
				base[offset + i] = tmp[i];
		}
	}

	// private final void setLeafKey(byte[] base, int idx, byte[] arr) {
	// if (arr.length != attrLength)
	// System.out.println("Array length not equal to LeafKey!");
	// else {
	// int offset= getLeafKeyOffset(idx);
	// for (int i= 0; i < attrLength; i++)
	// base[offset+i]= arr[i];
	// }
	// }

	private final void setLeafRID(byte[] base, int idx, byte[] arr) {
		if (arr.length != RM_Internal.RM_RID_SIZE)
			System.out.println("Array length not equal to size of RID!");
		else {
			int offset = getLeafRIDOffset(idx);
			for (int i = 0; i < RM_Internal.RM_RID_SIZE; i++)
				base[offset + i] = arr[i];
		}
	}

	private final int getLeafEntrySize() {
		return attrLength + RID.RID_SIZE;
	}

	private final int getLeafKeyOffset(int idx) {
		return PF_PageHandle.DATASTART_OFFSET + IX_Internal.IX_PAGEHDR_SIZE
				+ idx * leafEntrySize();
	}

	private final int getLeafRIDOffset(int idx) {
		return getLeafKeyOffset(idx) + attrLength;
	}

	private final void moveLeafKey(byte[] base, int srcIdx, int destIdx,
			int length) {
		int destOffset = getLeafKeyOffset(destIdx);
		int srcOffset = getLeafKeyOffset(srcIdx);

		if (srcIdx < destIdx) {
			for (int i = length - 1; i >= 0; i--)
				base[destOffset + i] = base[srcOffset + i];

			for (int i = 0; i < leafEntrySize(); i++)
				base[srcOffset + i] = (byte) 0;
		} else
			System.out.println("Wrong Index when moving LeafKey!");
	}

	private int compare(Object object, byte[] value) {
		return compare(object, value, 0);
	}

	private int compare(Object pData, byte[] pNode, int leafKeyOffset) {
		if (pData instanceof BytePointer) {
			return compare2(new BytePointer((BytePointer) pData).getArray(),
					pNode, leafKeyOffset);
		} else if (pData instanceof byte[]) {
			return compare2((byte[]) pData, pNode, leafKeyOffset);
		} else {
			return compare1(pData, pNode, leafKeyOffset);
		}
	}

	private int compare1(Object object, byte[] value, int offset) {
		int cmp = 0;
		int i;
		float f;
		switch (this.attrType) {
		case INT:
			i = ByteBuffer.wrap(value).getInt(offset);
			cmp = (Integer) object - i;
			// cmp = new Integer(i).compareTo((Integer) object);
			break;
		case FLOAT:
			f = ByteBuffer.wrap(value).getFloat(offset);
			cmp = (int) ((Float) object - f);
			// cmp = new Float(f).compareTo((Float) object);
			break;
		case STRING:
			byte[] strBuf = new byte[this.attrLength];
			System.arraycopy(value, offset, strBuf, 0, this.attrLength);
			String dataString = new String(strBuf, Charset.forName("ASCII"));
			// cmp = dataString.compareTo((String) object);
			String s = new String((String) object);
			cmp = s.compareTo(dataString);
			break;
		}
		return cmp;
	}

	private int compare2(byte[] _value, byte[] value, int offset) {
		int cmp = 0;
		int i, i0;
		float f, f0;
		switch (this.attrType) {
		case INT:
			i = ByteBuffer.wrap(value).getInt(offset);
			i0 = ByteBuffer.wrap(_value).getInt(0);
			// cmp = i - i0;
			cmp = i0 - i;
			break;
		case FLOAT:
			f = ByteBuffer.wrap(value).getFloat(offset);
			f0 = ByteBuffer.wrap(_value).getFloat(0);
			cmp = Float.compare(f, f0);
			cmp = -cmp;
			break;
		case STRING:
			byte[] strBuf = new byte[this.attrLength];
			System.arraycopy(value, offset, strBuf, 0, this.attrLength);
			String dataString = new String(strBuf, Charset.forName("ASCII"));
			cmp = dataString.compareTo(new String(_value, Charset
					.forName("ASCII")));
			cmp = -cmp;
			break;
		}
		return cmp;
	}

	private int compare3(byte[] _value, int _offset, byte[] value, int offset) {
		int cmp = 0;
		int i, i0;
		float f, f0;
		switch (this.attrType) {
		case INT:
			i = ByteBuffer.wrap(value).getInt(offset);
			i0 = ByteBuffer.wrap(_value).getInt(_offset);
			cmp = i - i0;
			break;
		case FLOAT:
			f = ByteBuffer.wrap(value).getFloat(offset);
			f0 = ByteBuffer.wrap(_value).getFloat(_offset);
			cmp = Float.compare(f, f0);
			break;
		case STRING:
			byte[] strBuf = new byte[this.attrLength];
			System.arraycopy(value, offset, strBuf, 0, this.attrLength);
			String dataString = new String(strBuf, Charset.forName("ASCII"));
			byte[] tmp = new byte[_value.length - _offset];
			System.arraycopy(_value, _offset, tmp, 0, tmp.length);
			cmp = dataString
					.compareTo(new String(tmp, Charset.forName("ASCII")));
			break;
		}
		return 0 - cmp;
	}

	//
	// InsertEntryToNode
	//
	// Desc: Insert a new index entry to a specific node or the subtree
	// accessible from it.
	//
	// If this node is internal:
	// 1. Find a subtree where the entry should be inserted.
	// 2. Recursively call InsertEntryToNode() for the subtree.
	// 3. If the traversed child node is not splitted, we're DONE.
	// 4. Otherwise, insert a new key/pointer pair propagated from
	// child to this node. If no space, split this node and
	// propagate split information to parent node.
	//
	// If this node is leaf:
	// 1. If enough space, just add the new entry into this node,
	// and we're DONE.
	// 2. Otherwise, split this node and propagate split information
	// to parent node.
	//
	// In: nodeNum -
	// pData/rid - index entry to be inserted
	// Out: splitKey/ - key/pointer pair which should be inserted to
	// splitNodeNum the parent node (as a result of split)
	// Ret: PF return code
	//
	private RC insertEntryToNode(int nodeNum, Object data, RID rid,
			BytePointer splitKey, PageNum splitNodeNum) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer node = new BytePointer();
		int j = 0;

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
			return rc;

		// Current node is LEAF node
		// bit calculate?
		if (((new IX_PageHdr(node.getArray(), PF_PageHandle.DATASTART_OFFSET)).flags & IX_Internal.IX_LEAF_NODE) != 0) {
			// unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
				return rc;

			// Insert new entry to leaf node
			if ((rc = insertEntryToLeafNode(nodeNum, data, rid, splitKey,
					splitNodeNum, 1)) != RC.SUCCESS)
				return rc;
		} else {
			// Current node is INTERNAL node
			int childNodeNum = PageNum.PF_PAGE_UNSET;

			// Find the right child to traverse
			// zliu 101
			IX_PageHdr _ixPageHdr = new IX_PageHdr(node.getArray(),
					PF_PageHandle.DATASTART_OFFSET);
			int _numKeys = _ixPageHdr.numKeys;
			for (j = 0; j < _numKeys; j++) {
				if (compare(data, internalKey(node.getArray(), j)) < 0)
					break;
			}

			childNodeNum = ByteBuffer.wrap(internalPtr(node.getArray(), j))
					.getInt(0);

			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
				return rc;

			// Recursively call InsertEntryToNode()
			// No clue whether the child is internal or leaf
			if ((rc = insertEntryToNode(childNodeNum, data, rid, splitKey,
					splitNodeNum)) != RC.SUCCESS)
				return rc;

			// Need to add new entry to this node
			// (traveresed child node has been splitted)
			if (splitNodeNum.getPageNum() != IX_Internal.IX_DONT_SPLIT)
				if ((rc = insertEntryToIntlNode(nodeNum, childNodeNum,
						splitKey, splitNodeNum)) != RC.SUCCESS)
					// should not happen
					return rc;
		}

		// return OK
		return RC.SUCCESS;
	}

	//
	// InsertEntryToLeafNode
	//
	private RC insertEntryToLeafNode(int nodeNum, Object data, RID rid,
			BytePointer splitKey, PageNum splitNodeNum, int originalLeaf) {
		// System.out.println("Run the 'insertEntryToLeafNode!");
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer node = new BytePointer();
		int numKeys = 0;
		int j = 0;

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
			return rc;

		// Read numKeys
		IX_PageHdr IxPageHdr = new IX_PageHdr(node.getArray(),
				PF_PageHandle.DATASTART_OFFSET);
		numKeys = IxPageHdr.numKeys;

		// Key already exists?
		for (j = numKeys - 1; j >= 0; j--)
			if (compare(data, leafKey(node.getArray(), j)) == 0)
				break;

		if (j == -1) {
			// Key not found: we're good
			if (originalLeaf != 0) {
				distinctValsInc++;
				// Unpin
				if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
					return rc;

				// Just add new entry if possible
				if (IX_Internal.IX_PAGEHDR_SIZE + (numKeys + 1)
						* leafEntrySize() <= Pf.PF_PAGE_SIZE) {
					if ((rc = insertEntryToLeafNodeNoSplit(nodeNum, data, rid,
							splitKey, splitNodeNum)) != RC.SUCCESS)
						return rc;
				} else {
					// Not enough room
					// Split LEAF node
					if (originalLeaf != 0) {
						if ((rc = insertEntryToLeafNodeSplit(nodeNum, data,
								rid, splitKey, splitNodeNum)) != RC.SUCCESS)
							return rc;
					} else {
						// Don't split any other leaf nodes but the original one
						return RC._9999;
					}
				}
				// zliu 5
				return RC.SUCCESS;
			} else {
				// No more recursion, don't insert here and go back
				// Unpin
				if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
					return rc;
				return RC._9999;
			}
		}

		// (Key,RID) already exists?
		for (; j >= 0; j--) {
			if (compare(data, leafKey(node.getArray(), j)) > 0) {
				// Unpin
				if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
					return rc;

				// Just add new entry if possible
				if (IX_Internal.IX_PAGEHDR_SIZE + (numKeys + 1)
						* leafEntrySize() <= Pf.PF_PAGE_SIZE) {
					if ((rc = insertEntryToLeafNodeNoSplit(nodeNum, data, rid,
							splitKey, splitNodeNum)) != RC.SUCCESS)
						return rc;
				} else {
					// Not enough room
					// Split LEAF node
					if (originalLeaf != 0) {
						if ((rc = insertEntryToLeafNodeSplit(nodeNum, data,
								rid, splitKey, splitNodeNum)) != RC.SUCCESS)
							return rc;
					} else {
						// Don't split any other leaf nodes but the original one
						return RC._9999;
					}
				}
				// zliu 6
				return RC.SUCCESS;
			}
			// Found
			if (Arrays.equals(rid.toBytes(), leafRID(node.getArray(), j))) {
				// Unpin
				if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
					return rc;

				return RC.IX_ENTRYEXISTS;
			}
		}

		// Need to proceed to the previous leaf node
		if (j == -1 && nodeNum != 0
				&& IxPageHdr.prevNode != IX_Internal.IX_NO_MORE_NODE) {
			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
				return rc;

			rc = insertEntryToLeafNode(IxPageHdr.prevNode, data, rid, splitKey,
					splitNodeNum, 0);

			if (rc.getValue() == -9999) {
				// Just add new entry if possible
				if (IX_Internal.IX_PAGEHDR_SIZE + (numKeys + 1)
						* leafEntrySize() <= Pf.PF_PAGE_SIZE) {
					if ((rc = insertEntryToLeafNodeNoSplit(nodeNum, data, rid,
							splitKey, splitNodeNum)) != RC.SUCCESS)
						return rc;
				} else {
					// Not enough room
					// Split LEAF node
					if (originalLeaf != 0) {
						if ((rc = insertEntryToLeafNodeSplit(nodeNum, data,
								rid, splitKey, splitNodeNum)) != RC.SUCCESS)
							return rc;
					} else {
						// Don't split any other leaf nodes but the original one
						return RC._9999;
					}
				}
			} else if (rc != RC.SUCCESS)
				return rc;

			return RC.SUCCESS;
		}

		// zliu 201
		if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS) {
			return rc;
		}
		numKeys = getNumKeys(node.getArray());
		if (IX_Internal.IX_PAGEHDR_SIZE + (numKeys + 1) * getLeafEntrySize() <= Pf.PF_PAGE_SIZE) {
			if ((rc = insertEntryToLeafNodeNoSplit(nodeNum, data, rid,
					splitKey, splitNodeNum)) != RC.SUCCESS) {
				return rc;
			}
		} else {
			if (originalLeaf != 0) {
				if ((rc = insertEntryToLeafNodeSplit(nodeNum, data, rid,
						splitKey, splitNodeNum)) != RC.SUCCESS) {
					return rc;
				}
			} else
				return RC._9999;
		}
		// Return OK
		return RC.SUCCESS;
	}

	//
	// InsertEntryToLeafNodeSplit
	//
	private RC insertEntryToLeafNodeSplit(int nodeNum, Object data, RID rid,
			BytePointer splitKey, PageNum splitNodeNum) {
//		System.out.println("Run the '&&&&&&&&&&&&&&&&&insertEntryToLeafNodeSplit");
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer pNode = new BytePointer();
		PF_PageHandle newPageHandle = new PF_PageHandle();
		BytePointer newNode = new BytePointer();
		PageNum refNewNodeNum = new PageNum(); // zliu 102
		int newNodeNum = PageNum.PF_PAGE_UNSET;
		int insertLocation = 0;
		int pivot = 0;

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(pNode)) != RC.SUCCESS)
			return rc;

		// Allocate a new LEAF node
		if ((rc = pfFileHandle.allocatePage(newPageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = newPageHandle.getData(newNode)) != RC.SUCCESS)
			return rc;
		// zliu 103
		if ((rc = newPageHandle.getPageNum(refNewNodeNum)) != RC.SUCCESS)
			return rc;
		newNodeNum = refNewNodeNum.getPageNum();

		// Select a boundary so that "half full" constraint is met
		pivot = this.getNumKeys(pNode.getArray()) / 2;
		if (compare(data, leafKey(pNode.getArray(), pivot)) > 0) {
			pivot++;
			insertLocation = 1;
		} else
			insertLocation = -1;

		// Move a half of data to new node
		int len = (this.getNumKeys(pNode.getArray()) - pivot) * leafEntrySize();
		int offset = getLeafKeyOffset(pivot);
		System.arraycopy(pNode.getArray(), offset, newNode.getArray(),
				PF_PageHandle.DATASTART_OFFSET + IX_Internal.IX_PAGEHDR_SIZE,
				len);

		// newNode.copyFromArray(PF_PageHandle.DATASTART_OFFSET
		// + IX_Internal.IX_PAGEHDR_SIZE,
		// leafKey(node.getArray(), pivot), 0,
		// (ixPageHdr.numKeys-pivot)*leafEntrySize());

		// Write node headers
		System.arraycopy(pNode.getArray(), PF_PageHandle.DATASTART_OFFSET,
				newNode.getArray(), PF_PageHandle.DATASTART_OFFSET,
				IX_Internal.IX_PAGEHDR_SIZE);
		// zliu 100
		putNumKeys(newNode.getArray(),
				(short) (getNumKeys(pNode.getArray()) - (short) pivot));
		putNumKeys(pNode.getArray(), (short) pivot);

		// Maintain doubly linked list
		putPrevNode(newNode.getArray(), nodeNum);
		putNextNode(pNode.getArray(), newNodeNum);

		if (nodeNum != 0
				&& getNextNode(newNode.getArray()) != IX_Internal.IX_NO_MORE_NODE) {
			PF_PageHandle ph = new PF_PageHandle();
			BytePointer pn = new BytePointer();

			// Pin
			if ((rc = pfFileHandle.getThisPage(getNextNode(newNode.getArray()),
					ph)) != RC.SUCCESS)
				return rc;
			if ((rc = ph.getData(pn)) != RC.SUCCESS)
				return rc;

			putPrevNode(pn.getArray(), newNodeNum);

			// Unpin
			if ((rc = pfFileHandle.markDirty(getNextNode(newNode.getArray()))) != RC.SUCCESS)
				return rc;
			if ((rc = pfFileHandle.unpinPage(getNextNode(newNode.getArray()))) != RC.SUCCESS)
				return rc;
		}

		// Insert
		if (insertLocation > 0) {
			if ((rc = insertEntryToLeafNodeNoSplit(newNodeNum, data, rid,
					splitKey, splitNodeNum)) != RC.SUCCESS)
				return rc;
		} else {
			if ((rc = insertEntryToLeafNodeNoSplit(nodeNum, data, rid,
					splitKey, splitNodeNum)) != RC.SUCCESS)
				return rc;
		}

		// zliu 116
		// Choose a key to propagate to parent node
		splitNodeNum.setPageNum(newNodeNum);
		// zliu 8
		// splitKey.setArray(new byte[RedBase.MAXSTRINGLEN]);
		splitKey.setArray(leafKey(newNode.getArray(), 0));

		// if define DEBUG_IX
		Assert.assertTrue(compare(splitKey.getArray(),
				leafKey(pNode.getArray(), (getNumKeys(pNode.getArray()) - 1))) >= 0);
		Assert.assertTrue(compare(splitKey.getArray(),
				leafKey(newNode.getArray(), 0)) <= 0);
		// end if
		// zliu 115

		// This LEAF node is ROOT!
		if (nodeNum == 0) {
			PF_PageHandle new2PageHandle = new PF_PageHandle();
			BytePointer new2Node = new BytePointer();
			int new2NodeNum = PageNum.PF_PAGE_UNSET;
			PageNum refNew2NodeNum = new PageNum();
			// Allocate a new Leaf Node
			if ((rc = pfFileHandle.allocatePage(new2PageHandle)) != RC.SUCCESS)
				return rc;
			if ((rc = new2PageHandle.getData(new2Node)) != RC.SUCCESS)
				return rc;
			// zliu 109
			if ((rc = new2PageHandle.getPageNum(refNew2NodeNum)) != RC.SUCCESS)
				return rc;
			new2NodeNum = refNew2NodeNum.getPageNum();

			// To assign page number 0 to root node
			System.arraycopy(pNode.getArray(), PF_PageHandle.DATASTART_OFFSET,
					new2Node.getArray(), PF_PageHandle.DATASTART_OFFSET,
					Pf.PF_PAGE_SIZE);
			// Arrays.fill(node.getArray(), PF_PageHandle.DATASTART_OFFSET,
			// node.getArray().length, (byte) 0);
			// zliu 9
			Arrays.fill(pNode.getArray(), PF_PageHandle.DATASTART_OFFSET,
					Pf.PF_PAGE_SIZE, (byte) 0);
			putFlags(pNode.getArray(), (short) IX_Internal.IX_INTERNAL_NODE);
			putNumKeys(pNode.getArray(), (short) 1);
			putPrevNode(pNode.getArray(), attrType.getValue());
			putNextNode(pNode.getArray(), attrLength);
			// zliu 107
			putPrevNode(new2Node.getArray(), IX_Internal.IX_NO_MORE_NODE);
			putNextNode(newNode.getArray(), IX_Internal.IX_NO_MORE_NODE);

			setInternalPtr(pNode.getArray(), 0,
					ByteBuffer.allocate(4).putInt(0, new2NodeNum).array());
			setInternalKey(pNode.getArray(), 0, splitKey.getArray());
			// zliu 104
			setInternalPtr(pNode.getArray(), 1,
					ByteBuffer.allocate(4).putInt(0, newNodeNum).array());
			// zliu 106
			System.out.println("Ptr 0 = " + new2NodeNum);
			System.out.println("Key 0 = "
					+ ByteBuffer.wrap(splitKey.getArray()).getInt(0));
			System.out.println("Ptr 1 = " + newNodeNum);
			// zliu 10
			putPrevNode(newNode.getArray(), new2NodeNum);

			// Unpin
			if ((rc = pfFileHandle.markDirty(new2NodeNum)) != RC.SUCCESS)
				return rc;
			if ((rc = pfFileHandle.unpinPage(new2NodeNum)) != RC.SUCCESS)
				return rc;

			// Reset
			splitNodeNum.setPageNum(IX_Internal.IX_DONT_SPLIT);
			// zliu 11
			splitKey.setArray(null);

			depthInc++;
		}

		// Unpin
		if ((rc = pfFileHandle.markDirty(nodeNum)) != RC.SUCCESS)
			return rc;
		// zliu 105
		if ((rc = pfFileHandle.markDirty(newNodeNum)) != RC.SUCCESS)
			return rc;
		if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
			return rc;
		// zliu 106
		if ((rc = pfFileHandle.unpinPage(newNodeNum)) != RC.SUCCESS)
			return rc;

		// Return OK
		return RC.SUCCESS;
	}

	//
	// InsertEntryToLeafNodeNoSplit
	//
	private RC insertEntryToLeafNodeNoSplit(int nodeNum, Object data, RID rid,
			BytePointer splitKey, PageNum splitNodeNum) {
		// System.out.println("Run the '****************insertEntryToLeafNodeNoSplit");
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer node = new BytePointer();
		int j = 0;

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
			return rc;

		// generate the ix_pagehdr from data
		IX_PageHdr ixPageHdr = new IX_PageHdr(node.getArray(),
				PF_PageHandle.DATASTART_OFFSET);

		// Find the right place
		for (j = 0; j < ixPageHdr.numKeys; j++) {
			// System.out.println("data is: " + (Integer)data);
			// byte[] arr= leafKey(node.getArray(), j);
			// ByteBuffer buf= ByteBuffer.wrap(arr);
			// int tmp= buf.getInt();
			// System.out.println("leafKey is: " + tmp);
			if (compare(data, leafKey(node.getArray(), j)) < 0) {
				// Make a "hole" for new entry
				int length = (ixPageHdr.numKeys - j) * leafEntrySize();
				moveLeafKey(node.getArray(), j, j + 1, length);
				break;
			}
		}

		// Fill out new key
		setLeafKey(node.getArray(), j, data, attrLength);
		// Fill out RID associated with new key
		setLeafRID(node.getArray(), j, rid.toBytes());
		// Increment #keys
		ixPageHdr.numKeys++;

		// write back to node
		ixPageHdr.writeBackNode(node, PF_PageHandle.DATASTART_OFFSET);

		// System.out.println("^^^^After insert the " + (Integer)data +
		// " entry^^^^^^^");
		// for (int i= 0; i < 200; i++) {
		// byte[] arr= leafKey(node.getArray(), i);
		// ByteBuffer bvf= ByteBuffer.wrap(arr);
		// System.out.print(bvf.getInt() + " ");
		// if (i != 0 && i % 20 == 0)
		// System.out.println();
		// }
		// System.out.println();

		// Unpin
		if ((rc = pfFileHandle.markDirty(nodeNum)) != RC.SUCCESS)
			return rc;
		if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
			return rc;

		// Reset
		splitNodeNum.setPageNum(IX_Internal.IX_DONT_SPLIT);
		// zliu 7
		splitKey.setArray(null);

		// Return OK
		return RC.SUCCESS;
	}

	//
	// InsertEntryToIntlNode
	//
	private RC insertEntryToIntlNode(int nodeNum, int childNodeNum,
			BytePointer splitKey, PageNum splitNodeNum) {
//		System.out.println("Run the 'insertEntryToIntlNode!");
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer node = new BytePointer();
		int numKeys = 0;

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
			return rc;

		// Read numKeys
		numKeys = new IX_PageHdr(node.getArray(),
				PF_PageHandle.DATASTART_OFFSET).numKeys;

		// Unpin
		if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
			return rc;

		// Just add new entry if possible
		if (IX_Internal.IX_PAGEHDR_SIZE + (numKeys + 2) * internalEntrySize() <= Pf.PF_PAGE_SIZE) {
			if ((rc = insertEntryToIntlNodeNoSplit(nodeNum, childNodeNum,
					splitKey, splitNodeNum)) != RC.SUCCESS)
				return rc;
		} else {
			// Split INTERNAL node
			if ((rc = insertEntryToIntlNodeSplit(nodeNum, childNodeNum,
					splitKey, splitNodeNum)) != RC.SUCCESS)
				return rc;
		}

		// Return OK
		return RC.SUCCESS;
	}

	//
	// InsertEntryToIntlNodeSplit
	//
	private RC insertEntryToIntlNodeSplit(int nodeNum, int childNodeNum,
			BytePointer splitKey, PageNum splitNodeNum) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer node = new BytePointer();
		PF_PageHandle newPageHandle = new PF_PageHandle();
		BytePointer newNode = new BytePointer();
		int newNodeNum = PageNum.PF_PAGE_UNSET;
		int insertLocation, pivot = 0;
		byte[] newSplitKey = null;
		int j = 0;

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
			return rc;

		// generate the ix_pageHdr
		IX_PageHdr ixPageHdr = new IX_PageHdr(node.getArray(),
				PF_PageHandle.DATASTART_OFFSET);

		// Allocate a new INTERNAL node
		if ((rc = pfFileHandle.allocatePage(newPageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = newPageHandle.getData(newNode)) != RC.SUCCESS)
			return rc;
		PageNum refNewNodeNum = new PageNum();
		if ((rc = newPageHandle.getPageNum(refNewNodeNum)) != RC.SUCCESS)
			return rc;
		newNodeNum = refNewNodeNum.getPageNum();
		// Should respect the original order among duplicated keys
		for (j = 0; j < ixPageHdr.numKeys; j++) {
			byte[] arr = Arrays.copyOf(internalPtr(node.getArray(), j),
					PageNum.PAGENUM_SIZE);
			if (ByteArrayUtility.getInt(arr, 0) == childNodeNum)
				break;
		}

		// if define debug_ix
		Assert.assertTrue(j <= ixPageHdr.numKeys);
		// end if

		newSplitKey = new byte[RedBase.MAXSTRINGLEN];

		// Select a boundary so that "half full" constraint is met
		pivot = (ixPageHdr.numKeys + 1) / 2;
		if (j > pivot)
			insertLocation = 1; // right
		else if (j < pivot) {
			pivot--;
			insertLocation = -1; // left
		} else
			insertLocation = 0; // to parent

		// Move a half of data to new node
		if (insertLocation == 0) {
			copyInternalKey(newNode.getArray(), 0, node.getArray(), pivot,
					(ixPageHdr.numKeys - pivot) * internalEntrySize());
			setInternalPtr(newNode.getArray(), 0, splitNodeNum.toBytes());
			// newSplitKey.setArray(splitKey.getArray(), RedBase.MAXSTRINGLEN);
			System.arraycopy(splitKey.getArray(), 0, newSplitKey, 0,
					Math.min(RedBase.MAXSTRINGLEN, splitKey.getArray().length));
		} else {
			// zliu 2
			copyInternalPtr(newNode.getArray(), 0, node.getArray(), pivot + 1,
					(ixPageHdr.numKeys - pivot) * internalEntrySize());
			// newSplitKey.setArray(internalKey(node.getArray(), pivot),
			// attrLength);
			System.arraycopy(node.getArray(), getInternalKeyOffset(pivot),
					newSplitKey, 0, attrLength);
		}

		// Write node headers
		// newNode.setArray(node.getArray(), IX_Internal.IX_PAGEHDR_SIZE);
		System.arraycopy(node.getArray(), PF_PageHandle.DATASTART_OFFSET,
				newNode.getArray(), PF_PageHandle.DATASTART_OFFSET,
				IX_Internal.IX_PAGEHDR_SIZE);
		IX_PageHdr newIxPageHdr = new IX_PageHdr(newNode.getArray(),
				PF_PageHandle.DATASTART_OFFSET);
		newIxPageHdr.numKeys = (short) (ixPageHdr.numKeys - pivot - insertLocation
				* insertLocation);
		ixPageHdr.numKeys = (short) pivot;

		// Maintain doubly linked list
		newIxPageHdr.prevNode = nodeNum;
		ixPageHdr.nextNode = newNodeNum;

		newIxPageHdr.writeBackNode(newNode, PF_PageHandle.DATASTART_OFFSET);
		ixPageHdr.writeBackNode(node, PF_PageHandle.DATASTART_OFFSET);

		if (nodeNum != 0
				&& newIxPageHdr.nextNode != IX_Internal.IX_NO_MORE_NODE) {
			PF_PageHandle ph = new PF_PageHandle();
			BytePointer pn = new BytePointer();

			// Pin
			if ((rc = pfFileHandle.getThisPage(newIxPageHdr.nextNode, ph)) != RC.SUCCESS)
				return rc;
			if ((rc = ph.getData(pn)) != RC.SUCCESS)
				return rc;

			IX_PageHdr page = new IX_PageHdr(pn.getArray(),
					PF_PageHandle.DATASTART_OFFSET);
			page.prevNode = newNodeNum;
			page.writeBackNode(pn, PF_PageHandle.DATASTART_OFFSET);

			// Unpin
			if ((rc = pfFileHandle.markDirty(newIxPageHdr.nextNode)) != RC.SUCCESS)
				return rc;
			if ((rc = pfFileHandle.unpinPage(newIxPageHdr.nextNode)) != RC.SUCCESS)
				return rc;
		}

		// Insert
		if (insertLocation > 0) {
			if ((rc = insertEntryToIntlNodeNoSplit(newNodeNum, childNodeNum,
					splitKey, splitNodeNum)) != RC.SUCCESS)
				return rc;
		} else if (insertLocation < 0) {
			if ((rc = insertEntryToIntlNodeNoSplit(nodeNum, childNodeNum,
					splitKey, splitNodeNum)) != RC.SUCCESS)
				return rc;
		}

		splitNodeNum.setPageNum(newNodeNum);
		splitKey.setArray(newSplitKey);

		// if define DEBUG_IX
		Assert.assertTrue(compare(newSplitKey,
				internalKey(node.getArray(), ixPageHdr.numKeys - 1)) >= 0);
		Assert.assertTrue(compare(newSplitKey,
				internalKey(newNode.getArray(), 0)) <= 0);
		// end if

		// This INTERNAL node is ROOT!
		if (nodeNum == 0) {
			PF_PageHandle new2PageHandle = new PF_PageHandle();
			BytePointer new2Node = new BytePointer();
			int new2NodeNum = PageNum.PF_PAGE_UNSET;

			// Allocate a new LEAF node
			if ((rc = pfFileHandle.allocatePage(new2PageHandle)) != RC.SUCCESS)
				return rc;
			if ((rc = new2PageHandle.getData(new2Node)) != RC.SUCCESS)
				return rc;
			PageNum refNew2NodeNum = new PageNum();
			if ((rc = new2PageHandle.getPageNum(refNew2NodeNum)) != RC.SUCCESS)
				return rc;
			new2NodeNum = refNew2NodeNum.getPageNum();

			// To assign page number 0 to root node
			System.arraycopy(node.getArray(), PF_PageHandle.DATASTART_OFFSET,
					new2Node.getArray(), PF_PageHandle.DATASTART_OFFSET,
					Pf.PF_PAGE_SIZE);
			// node.setArray(new byte[Pf.PF_PAGE_SIZE], Pf.PF_PAGE_SIZE);
			// zliu 3
			// Arrays.fill(node.getArray(), PF_PageHandle.DATASTART_OFFSET,
			// node.getArray().length, (byte) 0);
			Arrays.fill(node.getArray(), PF_PageHandle.DATASTART_OFFSET,
					Pf.PF_PAGE_SIZE, (byte) 0);
			ixPageHdr.setIxPageHdr(node.getArray(),
					PF_PageHandle.DATASTART_OFFSET);
			ixPageHdr.flags = IX_Internal.IX_INTERNAL_NODE;
			ixPageHdr.numKeys = 1;
			ixPageHdr.prevNode = attrType.getValue();
			ixPageHdr.nextNode = attrLength;

			ixPageHdr.writeBackNode(node, PF_PageHandle.DATASTART_OFFSET);

			ByteBuffer tmpBuf = ByteBuffer.allocate(4);
			tmpBuf.putInt(0, new2NodeNum);
			setInternalPtr(node.getArray(), 0, tmpBuf.array());
			setInternalKey(node.getArray(), 0, splitKey.getArray());
			tmpBuf.putInt(0, newNodeNum);
			setInternalPtr(node.getArray(), 1, tmpBuf.array());

			//
			newIxPageHdr.prevNode = new2NodeNum;
			newIxPageHdr.writeBackNode(newNode, PF_PageHandle.DATASTART_OFFSET);

			// Unpin
			if ((rc = pfFileHandle.markDirty(new2NodeNum)) != RC.SUCCESS)
				return rc;
			if ((rc = pfFileHandle.unpinPage(new2NodeNum)) != RC.SUCCESS)
				return rc;

			// Reset
			splitNodeNum.setPageNum(IX_Internal.IX_DONT_SPLIT);
			// zliu 4
			splitKey.setArray(null);

			depthInc++;
		}

		// write back to node
		ixPageHdr.writeBackNode(node, PF_PageHandle.DATASTART_OFFSET);

		// Unpin
		if ((rc = pfFileHandle.markDirty(nodeNum)) != RC.SUCCESS)
			return rc;
		if ((rc = pfFileHandle.markDirty(newNodeNum)) != RC.SUCCESS)
			return rc;
		if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
			return rc;
		if ((rc = pfFileHandle.unpinPage(newNodeNum)) != RC.SUCCESS)
			return rc;

		// Return OK
		return RC.SUCCESS;
	}

	//
	// InsertEntryToIntlNodeNoSplit
	//
	private RC insertEntryToIntlNodeNoSplit(int nodeNum, int childNodeNum,
			BytePointer splitKey, PageNum splitNodeNum) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer node = new BytePointer();
		int j;

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS)
			return rc;
		if ((rc = pageHandle.getData(node)) != RC.SUCCESS)
			return rc;

		// generate a new IX_PageHdr from node
		IX_PageHdr ixPageHdr = new IX_PageHdr(node.getArray(),
				PF_PageHandle.DATASTART_OFFSET);

		// Should respect the original order among duplicated keys
		for (j = 0; j < ixPageHdr.numKeys; j++) {
			// Should care about the size of InternalPtr()
			byte[] arr = Arrays.copyOf(internalPtr(node.getArray(), j),
					PageNum.PAGENUM_SIZE);
			if (ByteArrayUtility.getInt(arr, 0) == childNodeNum) {
				// Make a "hole" for new entry
				int length = (ixPageHdr.numKeys - j) * internalEntrySize();
				moveInternalKey(node.getArray(), j, j + 1, length);
				break;
			}
		}

		// Fill out new key
		setInternalKey(node.getArray(), j, splitKey.getArray());
		// Fill out node associated with new key
		// zliu 110
		setInternalPtr(node.getArray(), j + 1, splitNodeNum.toBytes());
		// Increment #keys
		ixPageHdr.numKeys++;

		ixPageHdr.writeBackNode(node, PF_PageHandle.DATASTART_OFFSET);

		// Unpin
		if ((rc = pfFileHandle.markDirty(nodeNum)) != RC.SUCCESS)
			return rc;
		if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
			return rc;

		// Reset
		splitNodeNum.setPageNum(IX_Internal.IX_DONT_SPLIT);
		// zliu 1
		splitKey.setArray(null);

		// Return OK
		return RC.SUCCESS;
	}

	//
	// DeleteEntryAtNode
	//
	// Desc: Delete an existing index entry from a specific node or the
	// subtree accessible from it.
	// Lazy deletion.
	//
	// If this node is internal:
	// 1. Find a subtree using the key.
	// 2. Recursively call DeleteEntryAtNode() for the subtree.
	// 3. If the smallest value of the subtree is changed, update
	// the value (if the traversed subtree is leftmost one,
	// just propagate this infomation to parent)
	// 4. If the subtree is deleted, delete the corresponding
	// key/pointer pair. At this step, the smallest value of
	// the subtree might be changed, too. If no pointer left,
	// delete this node and propagate this information to parent.
	// Note: Different from insertion, the changed subtree might
	// not be accessible from pointers in this node because
	// of duplicates. When necessary, the doubly linked
	// list is used to handle this situation.
	//
	// If this node is leaf:
	// 1. Find the entry. It can be at previous node since we
	// traversed to the rightmost leaf node with key.
	// 2. If 2+ entries, just delete the new entry. If the smallest
	// value of the leaf node is changed, propagate the new
	// smallest key to parent node.
	// 3. Otherwise, delete the leaf node and propagate information
	// to parent node so that the parent node can be updated
	// accordingly.
	//
	// In: nodeNum -
	// pData/rid - index entry to be deleted
	// Out: smallestKey - key/pointer pair which should be inserted to
	// deletedNodeNum -
	// Ret: IX_ENTRYNOTFOUND, PF return code
	//
	private RC deleteEntryAtNode(int nodeNum, Object pData, RID rid,
			BytePointer refSmallestKey, PageNum deletedNodeNum) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer refpNode = new BytePointer();
		byte[] pNode = null;
		int j;

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS) {
			return rc;
		}

		if ((rc = pageHandle.getData(refpNode)) != RC.SUCCESS) {
			return rc;
		}

		pNode = refpNode.getArray();
		short _flags = ByteBuffer.wrap(pNode).getShort(
				PF_PageHandle.DATASTART_OFFSET + IX_PageHdr.getFlagsOffset());
		// Current node is LEAF node
		if ((_flags & IX_Internal.IX_LEAF_NODE) != 0) {
			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS) {
				return rc;
			}
			//
			if ((rc = deleteEntryAtLeafNode(nodeNum, pData, rid,
					refSmallestKey, deletedNodeNum)) != RC.SUCCESS) {
				return rc;
			}
		}
		// Current node is INTERNAL node
		else {
			int childNodeNum = PageNum.PF_PAGE_UNSET;

			// Find the right child to traverse
			short _numKeys = ByteBuffer.wrap(pNode).getShort(
					PF_PageHandle.DATASTART_OFFSET
							+ IX_PageHdr.getNumKeysOffset());
			for (j = 0; j < _numKeys; j++) {
				if (compare(pData, pNode, getInternalKeyOffset(j)) < 0)
					break;
			}

			childNodeNum = ByteArrayUtility.getInt(pNode,
					getInternalPtrOffset(j));

			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS) {
				return (rc);
			}

			// Recursion
			if ((rc = deleteEntryAtNode(childNodeNum, pData, rid,
					refSmallestKey, deletedNodeNum)) != RC.SUCCESS) {
				return (rc);
			}
			byte[] smallestKey = refSmallestKey.getArray();
			// Update the smallest key value
			if (smallestKey != null && j > 0) {

				Assert.assertTrue(deletedNodeNum.getPageNum() == IX_Internal.IX_NOT_DELETED);

				// Pin
				if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS)
					return rc;
				if ((rc = pageHandle.getData(refpNode)) != RC.SUCCESS) {
					return rc;
				}

				pNode = refpNode.getArray();
				//
				System.arraycopy(smallestKey, 0, pNode,
						getInternalKeyOffset(j - 1), attrLength);

				refSmallestKey.setArray(null);
				// Unpin
				if ((rc = pfFileHandle.markDirty(nodeNum)) != RC.SUCCESS) {
					return rc;
				}
				if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS) {
					return rc;
				}
			}

			// Traversed child node was disposed
			if (deletedNodeNum.getPageNum() != IX_Internal.IX_NOT_DELETED) {
				if ((rc = deleteEntryAtIntlNode(nodeNum, refSmallestKey,
						deletedNodeNum)) != RC.SUCCESS) {
					return rc;
				}
			}
		}

		return RC.SUCCESS;
	}

	private RC deleteEntryAtLeafNode(int nodeNum, Object pData, RID rid,
			BytePointer refSmallestKey, PageNum deletedNodeNum) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer refpNode = new BytePointer();
		byte[] pNode = null;
		int j;

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS) {
			return this.errReturn(rc);
		}
		if ((rc = pageHandle.getData(refpNode)) != RC.SUCCESS) {
			return this.errReturn(rc);
		}
		pNode = refpNode.getArray();

		short _numKeys;
		short _flags;
		int _prevNode;
		int _nextNode;

		_numKeys = ByteBuffer.wrap(pNode).getShort(
				PF_PageHandle.DATASTART_OFFSET + IX_PageHdr.getNumKeysOffset());
		// Find the right place (by search key)
		for (j = _numKeys - 1; j >= 0; j--)
			if (compare(pData, pNode, getLeafKeyOffset(j)) == 0)
				break;

		// Search key not found
		if (j == -1) {
			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS) {
				return this.errReturn(rc);
			}

			return RC.IX_ENTRYNOTFOUND;
		}

		ByteBuffer buf = ByteBuffer.wrap(pNode);
		// Find the right place (by RID)
		for (; j >= 0; j--) {
			if (compare(pData, pNode, getLeafKeyOffset(j)) > 0) {
				// Unpin
				if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
					return errReturn(rc);

				return (RC.IX_ENTRYNOTFOUND);
			}

			// Found
			if (rid.equals(new RID(buf.getInt(getLeafRIDOffset(j)), buf
					.getInt(getLeafRIDOffset(j) + 4)))) {
				break;
			}
		}

		// Need to proceed to the previous leaf node
		if (j == -1 && nodeNum != 0) {
			int prevNode = ByteBuffer.wrap(pNode).getInt(
					PF_PageHandle.DATASTART_OFFSET
							+ IX_PageHdr.getPrevNodeOffset());

			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS)
				return this.errReturn(rc);

			// No more node
			if (prevNode == IX_Internal.IX_NO_MORE_NODE)
				return (RC.IX_ENTRYNOTFOUND);

			return deleteEntryAtLeafNode(prevNode, pData, rid, refSmallestKey,
					deletedNodeNum);
		}
		// Found
		else {
			// The only key
			_numKeys = ByteBuffer.wrap(pNode).getShort(
					PF_PageHandle.DATASTART_OFFSET
							+ IX_PageHdr.getNumKeysOffset());
			if (_numKeys == 1 && nodeNum != 0) {
				Assert.assertTrue(j == 0);
				deletedNodeNum.setPageNum(nodeNum);
				refSmallestKey.setArray(null);

				_prevNode = ByteBuffer.wrap(pNode).getInt(
						PF_PageHandle.DATASTART_OFFSET
								+ IX_PageHdr.getPrevNodeOffset());
				_nextNode = ByteBuffer.wrap(pNode).getInt(
						PF_PageHandle.DATASTART_OFFSET
								+ IX_PageHdr.getNextNodeOffset());
				linkTwoNodesEachOther(_prevNode, _nextNode);

				// Dispose
				if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS) {
					return this.errReturn(rc);
				}

				if ((rc = pfFileHandle.disposePage(nodeNum)) != RC.SUCCESS) {
					return this.errReturn(rc);
				}
			}
			// Not the only key
			else {
				deletedNodeNum.setPageNum(IX_Internal.IX_NOT_DELETED);

				// Compute the smallest value
				_prevNode = ByteBuffer.wrap(pNode).getInt(
						PF_PageHandle.DATASTART_OFFSET
								+ IX_PageHdr.getPrevNodeOffset());
				if (j == 0
						&& nodeNum != 0
						&& _prevNode != IX_Internal.IX_NO_MORE_NODE
						&& compare3(pNode, getLeafKeyOffset(0), pNode,
								getLeafKeyOffset(1)) < 0) {
					byte[] smallestKeyBuf = new byte[RedBase.MAXSTRINGLEN];
					System.arraycopy(pNode, getLeafKeyOffset(1),
							smallestKeyBuf, 0, attrLength);
					refSmallestKey.setArray(smallestKeyBuf);
				} else
					refSmallestKey.setArray(null);

				// Remove the found entry
				_numKeys = ByteBuffer.wrap(pNode).getShort(
						PF_PageHandle.DATASTART_OFFSET
								+ IX_PageHdr.getNumKeysOffset());
				System.arraycopy(pNode, getLeafKeyOffset(j + 1), pNode,
						getLeafKeyOffset(j), (_numKeys - j - 1)
								* getLeafEntrySize());

				// Decrement #keys
				ByteArrayUtility.putShort(pNode, PF_PageHandle.DATASTART_OFFSET
						+ IX_PageHdr.getNumKeysOffset(), --_numKeys);

				// Unpin
				if ((rc = pfFileHandle.markDirty(nodeNum)) != RC.SUCCESS) {
					return errReturn(rc);
				}
				if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS) {
					return errReturn(rc);
				}
			}
		}

		// Return ok
		return RC.SUCCESS;
	}

	//
	// DeleteEntryAtIntlNode
	//
	private RC deleteEntryAtIntlNode(int nodeNum, BytePointer refSmallestKey,
			PageNum deletedNodeNum) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		BytePointer refpNode = new BytePointer();
		byte[] pNode = null;
		int j;
		int tempInt = Integer.MIN_VALUE;

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS) {
			return rc;
		}

		if ((rc = pageHandle.getData(refpNode)) != RC.SUCCESS) {
			return rc;
		}

		pNode = refpNode.getArray();

		short _numKeys = ByteBuffer.wrap(pNode).getShort(
				PF_PageHandle.DATASTART_OFFSET + IX_PageHdr.getNumKeysOffset());
		int _prevNode;
		int _nextNode;
		// Should respect the original order among duplicated keys
		for (j = _numKeys; j >= 0; j--) {
			tempInt = ByteArrayUtility.getInt(pNode,
					this.getInternalPtrOffset(j));
			if (deletedNodeNum.getPageNum() == tempInt) {
				break;
			}
		}

		// Need to proceed to the previous internal node
		if (j == -1 && nodeNum != 0) {
			int prevNode = ByteBuffer.wrap(pNode).getInt(
					PF_PageHandle.DATASTART_OFFSET
							+ IX_PageHdr.getPrevNodeOffset());

			// Unpin
			if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS) {
				return rc;
			}

			Assert.assertTrue(prevNode != IX_Internal.IX_NO_MORE_NODE);

			return deleteEntryAtIntlNode(prevNode, refSmallestKey,
					deletedNodeNum);
		}
		// Found
		else {
			// The only pointer
			_numKeys = ByteBuffer.wrap(pNode).getShort(
					PF_PageHandle.DATASTART_OFFSET
							+ IX_PageHdr.getNumKeysOffset());
			if (_numKeys == 0) {
				Assert.assertTrue(nodeNum != 0);
				deletedNodeNum.setPageNum(nodeNum);
				_prevNode = ByteBuffer.wrap(pNode).getInt(
						PF_PageHandle.DATASTART_OFFSET
								+ IX_PageHdr.getPrevNodeOffset());
				_nextNode = ByteBuffer.wrap(pNode).getInt(
						PF_PageHandle.DATASTART_OFFSET
								+ IX_PageHdr.getNextNodeOffset());
				linkTwoNodesEachOther(_prevNode, _nextNode);

				// Dispose
				if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS) {
					return rc;
				}
				if ((rc = pfFileHandle.disposePage(nodeNum)) != RC.SUCCESS) {
					return rc;
				}
			}
			// Not the only key
			else {
				deletedNodeNum.setPageNum(IX_Internal.IX_NOT_DELETED);

				// Compute the smallest value
				_prevNode = ByteBuffer.wrap(pNode).getInt(
						PF_PageHandle.DATASTART_OFFSET
								+ IX_PageHdr.getPrevNodeOffset());
				if (j == 0 && nodeNum != 0
						&& _prevNode != IX_Internal.IX_NO_MORE_NODE) {
					byte[] bufSmallestKey = new byte[RedBase.MAXSTRINGLEN];
					System.arraycopy(pNode, getInternalKeyOffset(0),
							bufSmallestKey, 0, attrLength);
					refSmallestKey.setArray(bufSmallestKey);
					_numKeys = ByteBuffer.wrap(pNode).getShort(
							PF_PageHandle.DATASTART_OFFSET
									+ IX_PageHdr.getNumKeysOffset());
					// Remove the found entry
					System.arraycopy(pNode, getInternalPtrOffset(1), pNode,
							getInternalPtrOffset(0), _numKeys
									* getInternalEntrySize());
				} else {
					refSmallestKey.setArray(null);
					// Remove the found entry
					_numKeys = ByteBuffer.wrap(pNode).getShort(
							PF_PageHandle.DATASTART_OFFSET
									+ IX_PageHdr.getNumKeysOffset());
					System.arraycopy(pNode, getInternalKeyOffset(j), pNode,
							getInternalKeyOffset(j - 1), (_numKeys - j)
									* getInternalEntrySize());
				}

				// Decrement #keys
				_numKeys = ByteBuffer.wrap(pNode).getShort(
						PF_PageHandle.DATASTART_OFFSET
								+ IX_PageHdr.getNumKeysOffset());
				ByteArrayUtility.putShort(pNode, PF_PageHandle.DATASTART_OFFSET
						+ IX_PageHdr.getNumKeysOffset(), --_numKeys);

				// Only one pointer remained at the ROOT node!
				if (nodeNum == 0 && _numKeys == 0) {
					int childNodeNum = PageNum.PF_PAGE_UNSET;
					PageNum refRootNodeNum = new PageNum();
					int rootNodeNum = PageNum.PF_PAGE_UNSET;
					BytePointer refpRootNode = new BytePointer();
					byte[] pRootNode = null;

					childNodeNum = ByteArrayUtility.getInt(pNode,
							getInternalPtrOffset(0));
					if ((rc = findNewRootNode(childNodeNum, refRootNodeNum,
							refpRootNode)) != RC.SUCCESS) {
						return rc;
					}

					rootNodeNum = refRootNodeNum.getPageNum();
					pRootNode = refpRootNode.getArray();

					// Move the new root node to page 0
					System.arraycopy(pRootNode, PF_PageHandle.DATASTART_OFFSET,
							pNode, PF_PageHandle.DATASTART_OFFSET,
							Pf.PF_PAGE_SIZE);
					ByteArrayUtility.putInt(
							pNode,
							PF_PageHandle.DATASTART_OFFSET
									+ IX_PageHdr.getPrevNodeOffset(),
							attrType.getValue());
					ByteArrayUtility.putInt(
							pNode,
							PF_PageHandle.DATASTART_OFFSET
									+ IX_PageHdr.getNextNodeOffset(),
							attrLength);

					// Unpin
					if ((rc = pfFileHandle.unpinPage(rootNodeNum)) != RC.SUCCESS) {
						return rc;
					}
					if ((rc = pfFileHandle.disposePage(rootNodeNum)) != RC.SUCCESS) {
						return rc;
					}
				}

				// Unpin
				if ((rc = pfFileHandle.markDirty(nodeNum)) != RC.SUCCESS) {
					return rc;
				}
				if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS) {
					return rc;
				}
			}
		}

		// Return ok
		return RC.SUCCESS;
	}

	//
	// LinkTwoNodesEachOther
	//
	// Desc: Link two nodes (at the same depth) each other
	// Maintains doubly linked list when a node is deleted
	// Called by DeleteEntryAtIntlNode() and DeleteEntryAtLeafNode()
	// Ret: PF return code
	//
	private RC linkTwoNodesEachOther(int prevNode, int nextNode) {
		RC rc = RC.SUCCESS;
		PF_PageHandle ph = new PF_PageHandle();
		BytePointer refpn = new BytePointer();
		byte[] pn = null;

		if (prevNode != IX_Internal.IX_NO_MORE_NODE) {
			// Pin
			if ((rc = pfFileHandle.getThisPage(prevNode, ph)) != RC.SUCCESS) {
				return rc;
			}
			if ((rc = ph.getData(refpn)) != RC.SUCCESS) {
				return rc;
			}
			pn = refpn.getArray();

			// Link
			ByteArrayUtility.putInt(pn, PF_PageHandle.DATASTART_OFFSET
					+ IX_PageHdr.getNextNodeOffset(), nextNode);

			// Unpin
			if ((rc = pfFileHandle.markDirty(prevNode)) != RC.SUCCESS) {
				return rc;
			}
			if ((rc = pfFileHandle.unpinPage(prevNode)) != RC.SUCCESS) {
				return rc;
			}
		}

		if (nextNode != IX_Internal.IX_NO_MORE_NODE) {
			// Pin
			if ((rc = pfFileHandle.getThisPage(nextNode, ph)) != RC.SUCCESS) {
				return this.errReturn(rc);
			}
			if ((rc = ph.getData(refpn)) != RC.SUCCESS) {
				return this.errReturn(rc);
			}
			pn = refpn.getArray();
			// Link
			ByteArrayUtility.putInt(pn, PF_PageHandle.DATASTART_OFFSET
					+ IX_PageHdr.getPrevNodeOffset(), prevNode);

			// Unpin
			if ((rc = pfFileHandle.markDirty(nextNode)) != RC.SUCCESS) {
				return this.errReturn(rc);
			}
			if ((rc = pfFileHandle.unpinPage(nextNode)) != RC.SUCCESS) {
				return this.errReturn(rc);
			}
		}

		// Return ok
		return RC.SUCCESS;
	}

	//
	// FindNewRootNode
	//
	// Desc: Recursively find the new root node when the old root node has
	// only one pointer due to deletions.
	// Dispose every node on the path from the old root to the new root.
	// Unpin is handled by caller.
	// Called by DeleteEntryAtIntlNode()
	// In: nodeNum
	// Out: rootNodeNum - set to the page number of new root node
	// pRootNode - set to the data pointer of new root node
	// Ret: PF return code
	//
	private RC findNewRootNode(int nodeNum, PageNum rootNodeNum,
			BytePointer refRootNode) {
		RC rc = RC.SUCCESS;
		PF_PageHandle pageHandle = new PF_PageHandle();
		byte[] pNode = null;
		BytePointer refpNode = new BytePointer();

		// Pin
		if ((rc = pfFileHandle.getThisPage(nodeNum, pageHandle)) != RC.SUCCESS) {
			return this.errReturn(rc);
		}

		if ((rc = pageHandle.getData(refpNode)) != RC.SUCCESS) {
			return this.errReturn(rc);
		}
		pNode = refpNode.getArray();

		short _flags;
		short _numKeys;
		int _prevNode;
		int _nextNode;

		_flags = ByteBuffer.wrap(pNode).getShort(
				PF_PageHandle.DATASTART_OFFSET + IX_PageHdr.getFlagsOffset());
		// Current node is LEAF node
		if ((_flags & IX_Internal.IX_LEAF_NODE) != 0) {
			// New root (leaf node)
			rootNodeNum.setPageNum(nodeNum);
			refRootNode.setArray(pNode);
		}

		// Current node is INTERNAL node
		else {
			// New root (internal node)
			_numKeys = ByteBuffer.wrap(pNode).getShort(
					PF_PageHandle.DATASTART_OFFSET
							+ IX_PageHdr.getNumKeysOffset());
			if (_numKeys > 0) {
				rootNodeNum.setPageNum(nodeNum);
				refRootNode.setArray(pNode);
			}
			// Dispose the current node and recurse if there is only one pointer
			else {
				int childNodeNum = PageNum.PF_PAGE_UNSET;
				childNodeNum = ByteArrayUtility.getInt(pNode,
						getInternalPtrOffset(0));

				// Dispose
				if ((rc = pfFileHandle.unpinPage(nodeNum)) != RC.SUCCESS) {
					return this.errReturn(rc);
				}
				if ((rc = pfFileHandle.disposePage(nodeNum)) != RC.SUCCESS) {
					return this.errReturn(rc);
				}

				// Recursion
				if ((rc = findNewRootNode(childNodeNum, rootNodeNum,
						refRootNode)) != RC.SUCCESS) {
					return this.errReturn(rc);
				}
			}
		}
		return RC.SUCCESS;
	}

	private short getFlags(byte[] pNode) {
		return ByteBuffer.wrap(pNode).getShort(
				PF_PageHandle.DATASTART_OFFSET + IX_PageHdr.getFlagsOffset());
	}

	private short getNumKeys(byte[] pNode) {
		return ByteBuffer.wrap(pNode).getShort(
				PF_PageHandle.DATASTART_OFFSET + IX_PageHdr.getNumKeysOffset());
	}

	private int getPrevNode(byte[] pNode) {
		return ByteBuffer.wrap(pNode)
				.getInt(PF_PageHandle.DATASTART_OFFSET
						+ IX_PageHdr.getPrevNodeOffset());
	}

	private int getNextNode(byte[] pNode) {
		return ByteBuffer.wrap(pNode)
				.getInt(PF_PageHandle.DATASTART_OFFSET
						+ IX_PageHdr.getNextNodeOffset());
	}

	private void putFlags(byte[] pNode, short flags) {
		ByteBuffer.wrap(pNode).putShort(
				PF_PageHandle.DATASTART_OFFSET + IX_PageHdr.getFlagsOffset(),
				flags);
	}

	private void putNumKeys(byte[] pNode, short numKeys) {
		ByteBuffer.wrap(pNode).putShort(
				PF_PageHandle.DATASTART_OFFSET + IX_PageHdr.getNumKeysOffset(),
				numKeys);
	}

	private void putPrevNode(byte[] pNode, int prevNode) {
		ByteBuffer.wrap(pNode)
				.putInt(PF_PageHandle.DATASTART_OFFSET
						+ IX_PageHdr.getPrevNodeOffset(), prevNode);
	}

	private void putNextNode(byte[] pNode, int nextNode) {
		ByteBuffer.wrap(pNode)
				.putInt(PF_PageHandle.DATASTART_OFFSET
						+ IX_PageHdr.getNextNodeOffset(), nextNode);
	}
}
